package LimitedTimeGame.Day_0218;

/**
 * @author zxc
 * @date 2023/02/18 08:49
 **/

import java.util.ArrayList;
import java.util.List;

/**
 * 题目 ：
 * 题目详述 ：
 * 给你一个函数f(x, y)和一个目标结果z，函数公式未知，请你计算方程f(x,y) == z所有可能的正整数数对x 和 y。
 * 满足条件的结果数对可以按任意顺序返回。
 * 尽管函数的具体式子未知，但它是单调递增函数，也就是说：
 * f(x, y) < f(x + 1, y)
 * f(x, y) < f(x, y + 1)
 *
 * 你的解决方案将按如下规则进行评判：
 *
 * 判题程序有一个由 CustomFunction 的 9 种实现组成的列表，以及一种为特定的 z 生成所有有效数对的答案的方法。
 * 判题程序接受两个输入：function_id（决定使用哪种实现测试你的代码）以及目标结果 z 。
 * 判题程序将会调用你实现的 findSolution 并将你的结果与答案进行比较。
 * 如果你的结果与答案相符，那么解决方案将被视作正确答案，即 Accepted 。
 *
 * 提示：
 * 1 <= function_id <= 9
 * 1 <= z <= 100
 * 题目保证f(x, y) == z的解处于1 <= x, y <= 1000的范围内。
 * 在 1 <= x, y <= 1000的前提下，题目保证f(x, y)是一个32 位有符号整数。
 *
 *
 */
public class FindSolution02 {
    /**
     * 思路 ：
     * 二分查找，来简化查找方式;
     * ===》
     * （1）由于f(x, y) < f(x + 1, y) || f(x, y) < f(x, y + 1),即，代表了当x/y固定时，那么f(x0 , y) / f(x , y0)是单调递增函数;
     * （2）即，固定x = x0，后通过二分查找，去寻找指定y0，使得f(x0,y0) == z;
     *
     * @param customfunction
     * @param z
     * @return
     */
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 1 ; i <= 1000 ; i++){
            int left = 1;
            int right = 1000;
            while(left < right){
                int mid = (left + right) / 2;
                if(customfunction.f(i , mid) >= z){
                    right = mid;
                }
                else {
                    left = mid + 1;
                }
            }
            if(customfunction.f(i , left) == z){
                List<Integer> list = new ArrayList<>();
                list.add(i);
                list.add(left);
                result.add(list);
            }
        }
        return result;
    }
    interface CustomFunction {
        // Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
        int f(int x, int y);
    };
}
